This patent specification contains material that is subject to copyright protection. The copyright owner has no objection to the reproduction of this patent specification or related materials from associated patent office files for the purposes of review, but otherwise reserves all copyright whatsoever.
1. Field of the Invention
The present invention relates to digital image compression and in particular to image compression in raster image processing systems where memory resources are limited.
2. Background
Image compression is widely used in color raster image processing systems such as those found in printers. Image compression is used in these systems to reduce the amount of memory required to store raster images in the stages between pixel generation and the time when the final output has been delivered from the printer. Reducing the amount of memory reduces the total system cost.
In color printing environments the total uncompressed size of a generated pixel images is often large and it is advantageous to avoid storing the entire image. Such pixel images are typically generated in raster or band order. In particular, pixels, scanlines, groups of scanlines, or tiles, are emitted in a stream from a raster image processor (RIP) that has as input an object graphic description of the page to be printed. In some simple cases this raster image data stream may be fed directly to a print engine. But in many circumstances this is not possible. This may be because the print engine requires real-time data delivery, because the image must be kept in case error recovery is required, or because the image must be kept for printing later in a duplexing system. Many other reasons exist. In systems where the raster image data must be kept, it is often fed to a compressor in a pipeline fashion such that intermediate storage between the RIP and the compressor is small compared with the total uncompressed image size. The output of the compressor is also considerably smaller than the uncompressed image size.
Many compression schemes can be used in this environment. One widely used method for color images is the baseline method of the Joint Photographic Experts Group (JPEG) standard. However compression using baseline JPEG standard and other methods suffers a number of serious flaws that make their use difficult in systems with limited memory resources. Existing compression schemes all exhibit one or more of the following flaws when presented with streamed input data:
The memory available to receive the compression data can be over-run. Compression schemes are typically highly data-dependent and without knowing details of the input data ahead of time it is not possible to predict what size output buffer will be required to accept the compressed data. This is a serious problem for systems with limited memory resources. Allocating a large output buffer is typically wasteful, and often still not a guarantee that the compressed data will fit. Some schemes exist that limit total compressed size by maintaining a sufficiently high compression factor on local regions of the image, but in these schemes it is not possible to trade off one part of the image that compresses well against another that does not.
For lossy compression schemes (such as baseline JPEG) the degree of loss must be selected ahead of time. Control of the degree of perceptual degradation (in short, loss) is a common method of controlling the output compression size. But this must generally be selected consistently across a whole image to achieve consistent visual quality, and must be selected at the start of the compression operation.
The image may become unnecessarily compressed. Where a high-loss setting is used for a compression operation, it may transpire that the image data compressed well and a less-lossy setting could have been used in comparison with the system""s available memory. A less-lossy setting would have resulted in higher final image quality which is advantageous.
The compression scheme may require random access to, or multiple passes over, the uncompressed image data. Some compression schemes exist that overcome one or more of the earlier problems by using either random access to the uncompressed image data or by performing multiple passes over it. But this is disadvantageous because it requires storage either of the uncompressed image data or of the original data that is used to generate the image data.
U.S. Pat. No. 5,761,345 publishes an image processing apparatus initially storing variable length codes corresponding to a significant frequency component, and variable length codes corresponding to a less significant frequency component. If while storing the variable length codes into the storage means, it is detected that the storage means is full (with variable length codes), the control means makes room for the storage of further variable length codes corresponding to the more significant frequency component by cancelling variable length codes stored in the storage means, which correspond to the less significant frequency component. However, the image processing apparatus suffers from the disadvantage in that it makes inefficient use of the storage means and the decompressed image may have relatively low image quality.
U.S. Pat. No. 5,748,786 publishes a method for one-pass compression into a fixed size buffer. The methods use a reversible DWT with embedded coding. The method suffers from the disadvantage in that it requires significant amount of input image line buffering, and a high cost to implement the suggested entropy coder with current technology, particularly when many such parallel encoders/decoders ate required in a real time application.
U.S. Pat. No. 5,815,097 publishes a method for a one-pass spatially embedded coder. The method, avoiding so called costly transform domain techniques (such as JPEG/DCT methods), supports fixed rate and fixed size applications for one-pass encoding and decoding. That is the image is compressed into a fixed size buffer, in one-pass, with a relatively small working line buffer, without the need to buffer the entire input image. However, by avoiding so called costly transform domain techniques, the method suffers from the disadvantage in that it either makes inefficient use of the storage means and the decompressed image may have relative low image quality, or requires the use of sophisticated and costly arithmetic coders, whose cost is high in current technology, particularly when many such parallel encoders/decoders are required in a real time application.
These problems may also occur in many other related raster image processing systems such as digital cameras and scanners.
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.
According to one aspect of the invention, there is provided a method of storing coded image data of an image in a storage of fixed memory size, wherein the image comprises a plurality of pixels and the method comprises the steps of arranging the image into a plurality of bands each comprising a predetermined number N of consecutive lines of pixels; buffering and processing said bands one by one in turn, wherein the processing step comprises the following sub-steps for each currently buffered said band: arranging the current band into a plurality of blocks of pixels of size Mxc3x97M, wherein M is equal to said predetermined number N; transforming said blocks of pixels to produce respective blocks of transform coefficients; partitioning the blocks of transform coefficients into a plurality of partitions wherein each partition comprises data from each said block of transform coefficients and at least one partition comprises data from at least one but not all bit-planes of each said block of transform coefficients, and wherein the plurality of partitions comprise a perceptually significant partition and a perceptually insignificant partition and partitions of varying perceptually significance there between; coding each said partition; and managing the storing of the said coded partitions in the storage of fixed memory size, wherein during the storing of said coded partitions if it is determined the storage is full a coded least perceptually significant partition currently stored in said buffer is overwritten by data from a coded more perceptually significant partition.
According to another aspect of the invention, there is provided a method of storing coded image data of an image in a storage of fixed memory size, wherein the image comprises a plurality of pixels and the method comprises the steps of: arranging the image into a plurality of bands each comprising a predetermined number N of consecutive lines of pixels; buffering and processing said bands one by one in turn, wherein the processing step comprises the following sub-steps for each currently buffered said band: arranging the current band into a plurality of blocks of pixels of size Mxc3x97M, wherein M is equal to said predetermined number N; transforming said blocks of pixels to produce respective blocks of transform coefficients; partitioning the blocks of transform coefficients into a plurality of partitions wherein each partition comprises data from each said block of transform coefficients and at least one partition comprises data from at least one but not all bit-planes of each said block of transform coefficients, and wherein the plurality of partitions comprise a perceptually significant partition and a perceptually insignificant partition and partitions of varying perceptually significance there between; coding each said partition; and managing the storing of the said coded partitions in the storage of fixed memory size, wherein during the storing of said coded partitions if it is determined the storage is full a coded least perceptually significant partition currently stored in said buffer is overwritten by data from a coded more perceptually significant partition, and wherein the managing step comprises the sub-steps of: assigning in said storage corresponding linked lists for said coded partitions; and determining during said storage of said coded partitions if the storage is full and if so freeing a said linked list of a coded least perceptually significant partition currently stored in said buffer allowing it to be overwritten by data from a coded more perceptually significant partition.
According to a still another aspect of the invention, there is provided a method of decoding an image, wherein the method comprising the steps of buffering respective coded data of bands of the image one by one in turn in storage of fixed memory size; processing the respective coded data of the bands of the image, wherein the processing step comprises the following sub-steps for each currently buffered said band: retrieving information from said storage on at least one linked list stored in said storage corresponding to at least one coded partition; retrieving from said storage said at least one partition utilising said information; decoding said retrieved at least one partition; reconstituting blocks of transform coefficients of size Mxc3x97M from said at least one decoded partition, wherein each decoded partition comprises data from blocks of transform coefficients, and wherein the at least one partition comprise a perceptually significant partition; inverse transforming said blocks of transform coefficients to produce respective blocks of pixels coefficients; and reconstituting the current band of said image from said blocks of pixels, wherein said band comprises a predetermined number N of lines of pixels and said M is equal to said predetermined number N.
According to a still another aspect of the invention, there is provided apparatus for storing coded image data of an image in storage of fixed memory size, wherein the image comprises a plurality of pixels and the apparatus comprises: a module for arranging the image into a plurality of bands each comprising a predetermined number N of consecutive lines of pixels; a buffer for buffering said bands one by one in turn; and a processor for processing a currently said buffered band, wherein the processor comprises: a module arranging the currently buffered band into a plurality of blocks of pixels of size Mxc3x97M, wherein M is equal to said predetermined number N; a transform module transforming said blocks of pixels to produce respective blocks of transform coefficients, a partitioning module for partitioning the blocks of transform coefficients into a plurality of partitions wherein each partition comprises data from each said block of transform coefficients and at least one partition comprises data from at least one but not all bit-planes of each said block of transform coefficients, and wherein the plurality of partitions comprise a perceptually significant partition and a perceptually insignificant partition and partitions of varying perceptually significance there between; a coder module for coding each said partition; and a manager module for managing the storing of the said coded partitions in the storage of fixed memory size, wherein during the storing of said coded partitions if it is determined the storage is full a coded least perceptually significant partition currently stored in said buffer is overwritten by data from a coded more perceptually significant partition.
According to a still another aspect of the invention, there is provided apparatus for storing coded image data of an image in storage of fixed memory size, wherein the image comprises a plurality of pixels and the apparatus comprises: a module for arranging the image into a plurality of bands each comprising a predetermined number N of consecutive lines of pixels; a buffer for buffering said bands one by one in turn; and a processor for processing a currently said buffered band, wherein the processor comprises: a module arranging the currently buffered band into a plurality of blocks of pixels of size Mxc3x97M, wherein M is equal to said predetermined number N; a transform module transforming said blocks of pixels to produce respective blocks of transform coefficients; a partitioning module for partitioning the blocks of transform coefficients into a plurality of partitions wherein each partition comprises data from each said block of transform coefficients and at least one partition comprises data from at least one but not all bit-planes of each said block of transform coefficients, and wherein the plurality of partitions comprise a perceptually significant partition and a perceptually insignificant partition and partitions of varying perceptually significance there between; a coder module for coding each said partition; and a manager module for managing the storing of the said coded partitions in the storage of fixed memory size, wherein during the storing of said coded partitions if it is determined the storage is full a coded least perceptually significant partition currently stored in said buffer is overwritten by data from a coded more perceptually significant partition, and wherein the manager module comprises: a module for assigning in said storage corresponding linked lists for said coded partitions; and a module for determining during said storage of said coded partitions if the storage is fill and if so freeing a said linked list of a coded least perceptually significant partition currently stored in said buffer allowing it to be overwritten by data from a coded more perceptually significant partition.
According to a still another aspect of the invention, there is provided apparatus for decoding an image, wherein the apparatus comprises: a module for buffering respective coded data of bands of the image one by one in turn in storage of fixed memory size; a processor for processing a currently buffered band of coded data, wherein the processor comprises: a module for retrieving information from said storage on at least one linked list stored in said storage corresponding to at least one coded partition of the currently buffered band of coded data; a module for retrieving from said storage said at least one partition utilising said information; a decoding module for decoding said retrieved at least one partition; a module for reconstituting blocks of transform coefficients of size Mxc3x97M from said at least one decoded partition, wherein each decoded partition comprises data from blocks of transform coefficients, and wherein the at least one partition comprise a perceptually significant partition; an inverse transform module for inverse transforming said blocks of transform coefficients to produce respective blocks of pixels coefficients; and a module for reconstituting the current band of said image from said blocks of pixels, wherein said band comprises a predetermined number N of lines of pixels and said M is equal to said predetermined number N.
According to a still another aspect of the invention, there is provided a computer program for storing coded image data of an image in a storage of fixed memory size, wherein the image comprises a plurality of pixels and the computer program comprises: means for arranging the image into a plurality of bands each comprising a predetermined number N of consecutive lines of pixels; means for buffering and processing said bands one by one in turn, wherein the processing means performs the following steps for each currently buffered said band: arranging the current band into a plurality of blocks of pixels of size Mxc3x97M, wherein M is equal to said predetermined number N; transforming said blocks of pixels to produce respective blocks of transform coefficients; partitioning the blocks of transform coefficients into a plurality of partitions wherein each partition comprises data from each said block of transform coefficients and at least one partition comprises data from at least one but not all bit-planes of each said block of transform coefficients, and wherein the plurality of partitions comprise a perceptually significant partition and a perceptually insignificant partition and partitions of varying perceptually significance there between; coding each said partition; and managing the storing of the said coded partitions in the storage of fixed memory size, wherein during the storing of said coded partitions if it is determined the storage is full a coded least perceptually significant partition currently stored in said buffer is overwritten by data from a coded more perceptually significant partition.
According to a still another aspect of the invention, there is provided a computer program for storing coded image data of an image in a storage of fixed memory size, wherein the image comprises a plurality of pixels and the computer program comprises: means for arranging the image into a plurality of bands each comprising a predetermined number N of consecutive lines of pixels; means for buffering and processing said bands one by one in turn, wherein the processing means performs the comprises the following steps for each currently buffered said band: arranging the current band into a plurality of blocks of pixels of size Mxc3x97M, wherein M is equal to said predetermined number N; transforming said blocks of pixels to produce respective blocks of transform coefficients; partitioning the blocks of transform coefficients into a plurality of partitions wherein each partition comprises data from each said block of transform coefficients and at least one partition comprises data from at least one but not all bit-planes of each said block of transform coefficients, and wherein the plurality of partitions comprise a perceptually significant partition and a perceptually insignificant partition and partitions of varying perceptually significance there between; coding each said partition; and managing the storing of the said coded partitions in the storage of fixed memory size, wherein during the storing of said coded partitions if it is determined the storage is full a coded least perceptually significant partition currently stored in said buffer is overwritten by data from a coded more perceptually significant partition, and wherein the managing step comprises the sub-steps of: assigning in said storage corresponding linked lists for said coded partitions; and determining during said storage of said coded partitions if the storage is fill and if so freeing a said linked list of a coded least perceptually significant partition currently stored in said buffer allowing it to be overwritten by data from a coded more perceptually significant partition.
According to a still another aspect of the invention, there is provided a computer program for decoding an image, wherein the computer program comprises: means for buffering respective coded data of bands of the image one by one in turn in storage of fixed memory size; and means for processing the respective coded data of the bands of the image, wherein the processing means performs the following steps for each currently buffered said band: retrieving information from said storage on at least one linked list stored in said storage corresponding to at least one coded partition; retrieving from said storage said at least one partition utilising said information; decoding said retrieved at least one partition; reconstituting blocks of transform coefficients of size Mxc3x97M from said at least one decoded partition, wherein each decoded partition comprises data from blocks of transform coefficients, and wherein the at least one partition comprise a perceptually significant partition; inverse transforming said blocks of transform coefficients to produce respective blocks of pixels coefficients; and reconstituting the current band of said image from said blocks of pixels, wherein said band comprises a predetermined number N of lines of pixels and said M is equal to said predetermined number N.